
/*
--------------------------------------------------------------------------------------------------------------------
Copyright (c) 2009, Brian Delgado
All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

* Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
* Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
* Neither the name of Portland State University nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
--------------------------------------------------------------------------------------------------------------------


  Input file expectations: Only A,C,T,G characters in file. 
  
  General implementation:

  1. The file is read in, in chunks of MATCH_SIZE
  2. For each chunk, insert it into a search tree at the appropriate place. Note the location in node->matches.
  3. If we detect that a chunk was already put in the tree, just update the existing tree node with the location of this chunk
  4. FSEEK to the next byte in the input file (e.g. backtrack)
  5. Continue until all chunks are in the tree.
  6. Perform user-specified searches
  
  Brian Delgado, brian.delgado [at] gmail.[com]
  Nelson Ijih, neliji[at]gmail.[com]
  Taibat Onaolapo Morakinyo, tomorakinyo[at]gmail.[com]
  
  CS 510 (Open Source - Summer 2009) and (Multi-Core Programming - Summer 2008)

  Updated: February 2010 (Scholarship Class)
  Updated: Summer 2009 (Open Source Class)
  Created: August 13, 2008 (Multi-Core Programming Class)
*/

#include <iostream>
#include <fstream>
#include <pthread.h>
#include <string.h>
#include <stdlib.h>
#include "options.h"
#include "dnascout.h"
#include "ticks.h"

unsigned long long clocks[4]={0};

using namespace std;

int main(int argc, char **argv)
{
  // Stats Instrumentation
  unsigned int uniquenodes=0;
  unsigned int *reused_nodes;

  unsigned int MATCH_SIZE=0;
  int argnum=1;
  char inname[MAX_FILE_NAME_LENGTH] = {"\0"}; // filename
  int actionSpecified=INVALID;

  unsigned int start=0;
  unsigned int end=0;
  unsigned int length=0;
  unsigned int verbose=0;
  unsigned int print_tree=0;

  int file_io=0;
  ofstream ofs ("tree.txt" , ios::out);
  char *printout=NULL; 
  int level=-1;

  char *searchstring=NULL;
  struct node *head=(struct node*)malloc(sizeof(node));

  // Initialize the top node in the tree
  initNode(head);

  if (argc == 1) {
    cout << "\nPlease consult documentation for syntax.";
    return 0;
  }

  // Interpret user arguments
  while (argnum < argc) {

    if (strcmp(argv[argnum],"-t")==0 && actionSpecified==INVALID) {
      // User entered the type of search they want to do
      argnum++;
      
      if (argnum >= argc) { // Make sure they specify something after -t
	cout << "\nInvalid syntax.";
	return 0;
      }

      // Figure out what search they want to do
      if (strcmp(argv[argnum], "parallel")==0) {
	// Parallel search
	actionSpecified=PARALLEL;
	argnum++;
	
      } else if (strcmp(argv[argnum], "partial")==0) {
	// Partial search
	actionSpecified=PARTIAL;
	argnum++;
      } else if (strcmp(argv[argnum], "sequential")==0) {
	// sequential search
	actionSpecified=SEQEXACT;
	argnum++;
      } else if (strcmp(argv[argnum], "exactfile")==0) {
	// File-based search
	actionSpecified=FROMFILE;
	argnum++;
	
	MATCH_SIZE=detectMatchSize_inFile();
	if (MATCH_SIZE < 3) {
	  cout << "\nInvalid match size detected in file: " << MATCH_SIZE;
	  return INVALID;
	}
	
      } else if (strcmp(argv[argnum], "interactive")==0) {
	actionSpecified=INTERACTIVE;
	argnum++;
      } else {
	cout << "\nUnexpected text found while looking for {parallel, partial, sequential, interactive}";
	return INVALID;
      }
      
    } else if (strcmp(argv[argnum],"-f")==0) {
      // User is specifying the input file name
      argnum++;

      if (argnum >= argc) {
	cout << "\nYou didn't specify a filename.";
	return -1;
      }

      if (strlen(argv[argnum]) > MAX_FILE_NAME_LENGTH) {
	cout << "\nFile name is too long. Max length is: " << MAX_FILE_NAME_LENGTH << "\n";
	return INVALID;
      }
      
      // Store the filename
      strcpy(inname, argv[argnum]);
      argnum++;
    } else if (strcmp(argv[argnum], "-s")==0) {
      // User is specifiying search string
      argnum++;

      if (argnum >= argc) {
	cout << "\nYou didn't specify a search string.";
	return -1;
      }

      MATCH_SIZE=strlen(argv[argnum]);

      searchstring = (char *) malloc(MATCH_SIZE+1);

      strcpy(searchstring,argv[argnum]);
      argnum++;
    } else if (strcmp(argv[argnum], "-start")==0) {
      argnum++;

      if (argnum >= argc) {
	cout << "\nYou didn't specify a starting position.";
	return -1;
      }

      start=atoi(argv[argnum]);
      argnum++;
    } else if (strcmp(argv[argnum], "-end")==0) {
      argnum++;

      if (argnum >= argc) {
        cout << "\nYou didn't specify an ending position.";
        return -1;
      }

      end=atoi(argv[argnum]);
      argnum++;
    } else if (strcmp(argv[argnum], "-len")==0) {
      argnum++;

      if (argnum >= argc) {
        cout << "\nYou didn't specify a length.";
        return -1;
      }

      length=atoi(argv[argnum]);
      MATCH_SIZE=length;
      argnum++;
    } else if (strcmp(argv[argnum], "-v")==0) {
      argnum++;
      verbose=ENABLED;
    } else if (strcmp(argv[argnum], "-p")==0) {
      argnum++;
      if (actionSpecified==INVALID) {
	actionSpecified=PRINT_TREE;
      }
      print_tree=ENABLED;
    } else {
	cout << "\nYou entered invalid command line argments. Please consult the user-guide.";
	return INVALID;
      }
      
  }

  // Make sure the user specified a file name
  if (inname[0] == '\0') {
    cout << "\nYou didn't specify a file name for input.";
    return 0;
  }

  // Allocate memory for tree efficiency instrumentation
  cout << "\nPlease wait while the genome data is read...";
  cout << "\nMatch size is: " << MATCH_SIZE;
 
  reused_nodes = (unsigned int*) malloc(MATCH_SIZE*sizeof(unsigned int));
  
  // Build tree from input file
  if (buildTree(MATCH_SIZE,uniquenodes,reused_nodes,head,inname,verbose) != 0 ){
    //tree was not built correctly...
    return INVALID;
  }
  
  // Do the user-specified action
  switch (actionSpecified) {
  case PARALLEL:
    parallelSearch(searchstring, head);
    break;
  case SEQEXACT:
    seqExactMatch(searchstring, head);
    break;
  case PARTIAL:
    partialMatchSearch(searchstring, start,end,head,inname,verbose);
    break;
  case FROMFILE:
    searchInput_inFile(head,MATCH_SIZE);
    break;
  case INTERACTIVE:
    interactive(head,length);
    break;
  case PRINT_TREE:
    break;
  default: //fixme: need to check for this before allocating memory, etc. 
    cout << "\nInvalid option specified. Please consult the user-guide.";
    return INVALID;
    break;

  }
  
  if (print_tree==ENABLED) {
    printout =(char*)malloc(MATCH_SIZE+1);

    cout << "\nPrinting the tree \n";
    cout << "\nString\t\t\t\tLocation(s)\n";
    
    if (ofs.good()) {
      file_io=ENABLED;
    }
    printTree(head,' ', level,printout,MATCH_SIZE,ofs,file_io);

    free(printout);
  }
  
  
  // Debug stats
  if (verbose==ENABLED) {
    cout << "\nRe-used nodes at each level.";
    cout << "\nTree Depth\tReused Nodes.";
    unsigned int index=0;
    for (index=0; index < MATCH_SIZE; index++) {
      cout << "\n" << (index+1) << "\t\t" << reused_nodes[index];
    }
    if (file_io==ENABLED) { // Do same for file io
      for (index=0; index < MATCH_SIZE; index++) {
	ofs << "\n" << (index+1) << "\t\t" << reused_nodes[index];
      }

    }
  }
  
  free(head);
  free(searchstring);
  free(reused_nodes);
  ofs.close();
  cout << "\n\n";
}

/* 
   This function determines the match size from the file input by reading the first search string. 
   There is an assumption that search strings are all the same length. This assumption is checked during runtime.
*/
int detectMatchSize_inFile()
{
  int length=0;
  ifstream ifs ("searchStrings.txt" , ifstream::in);
  char *searchstring=(char *)malloc(MAX_SEARCH_LEN);
  
  if (ifs.good()) {
    ifs >> searchstring;
    length=strlen(searchstring);
  } else {
    cout << "\nError detecting search string length.";
  }  

  free(searchstring);
  ifs.close();
  
  return length;
}

/*
 After forming the tree,now lets go thru the list of target strings from the searchStrings.txt file
 1. Open the input file containing the dna strings we want to search for
 2. While we are there are still dna strings in the input file, keep searching the tree.
*/
int searchInput_inFile(struct node *head, unsigned int MATCH_SIZE)
{
  char *dna_strand=(char *)malloc(MATCH_SIZE);
  int searchCounter=1;

  cout << "\n-------------------\nExact match searches from search file.";
  
  // Open the input file
  ifstream ifs ("searchStrings.txt" , ifstream::in);

  while (ifs.good()) {
    cout << "\n";
    ifs >> dna_strand;
    if (strlen(dna_strand) !=MATCH_SIZE) {
      cout << "\nError, detected a search string which doesn't match the length of the first search string in the file: " << dna_strand;
      return INVALID;
    }

    if (ifs.good() ) { // The previous read might have just reached the end of file
      cout << "\n" << searchCounter << ". " << dna_strand;
      
      if (strlen(dna_strand) <= MATCH_SIZE) {

	parallelSearch(dna_strand, head);
	searchCounter++;
      } else {
	cout << "\nThe tree needs to be built with a deeper depth of " << strlen(dna_strand) << ".  Currently it has a depth of " << MATCH_SIZE << ".";
      }
    }
  }

  free(dna_strand);
  ifs.close();
  return 0;
}

// Exact match sequential search
int seqExactMatch(char *searchstring, struct node *head)
{  
  char *reversed;
  char *flipped;
  char *flippedreversed;
  int MATCH_SIZE=strlen(searchstring);
  int level=0;
  int retval=0;
  unsigned long long start=0;
  unsigned long long end=0;

  reversed = (char *) malloc(MATCH_SIZE+1);
  flipped = (char*) malloc(MATCH_SIZE+1);
  flippedreversed = (char*) malloc(MATCH_SIZE+1);

  cout << "\n-------------------\nExact string match search\n";
  // Generate the other three string permutations from the input string.
  retval=MakeStringPermutations(searchstring,reversed,flipped,flippedreversed);

  if (retval==INVALID) {
    return retval;
  }

  start=getticks();

  cout << "\nSearching for original string: " << searchstring;

  level=0;
  seq_searchTree(head, level, searchstring, MATCH_SIZE );


  cout << "\nSearching for reversed string: " << reversed;

  level=0;
  seq_searchTree(head, level, reversed, MATCH_SIZE );


  cout << "\nSearching for flipped string: " << flipped;

  level=0;
  seq_searchTree(head, level, flipped, MATCH_SIZE );


  cout << "\nSearching for flipped and reversed string: " << flippedreversed;

  level=0;
  
  seq_searchTree(head, level, flippedreversed, MATCH_SIZE );
  end=getticks();

  cout << "\n-------------------";
  free(reversed);
  free(flipped);
  free(flippedreversed);
  return 0;
}

// Interactive search
int interactive(struct node *head, unsigned int length)
{
  char searchstring[256]; // fixme
  if (length > 256) {
    cout << "\nLength too long. Max is 256 for now.";
    return 0;
  }

  memset(searchstring, 0, sizeof(searchstring));

  do {
    cout << "\nEnter search string or 'quit' to exit: ";
    cin >> searchstring;
    // Check length here, fixme
    if (strcmp(searchstring, "quit")==0) {
      return 0;
    }

    if (strlen(searchstring) != length) {
      cout << "\nInvalid length. Need length: " << " but found length: " << strlen(searchstring);
    } else {

      parallelSearch(searchstring, head);
    }
  } while (strcmp(searchstring, "quit") !=0);

  return 0;

}
// Partial match search
int partialMatchSearch(char *searchstring, int start, int end, struct node *head, char *inname, unsigned int verbose)
{
  int partialMatchSize=0;
  int invalidPartial=0;
  unsigned int uniquenodes=0;
  unsigned int *reused_nodes;
  int level=0;
  int retval=0;

  // for snippet
  char *subStringSearch;
  char *subReversed;
  char *subFlipped;
  char *subFlippedReversed;

  if (end > (int)strlen(searchstring)) {
    cout << "\nError: Ending is after the length of the search string.";
    invalidPartial=1;
  }
  
  // Check for invalid start and ends
  if (end <= start || end < 0 || start < 0) {
    cout << "\nError: You did not provide a valid start and ending position match. Start: " << start << ". End: " << end;
    invalidPartial=1;
  }
  
  if (invalidPartial==0) {
    
    //Find sub string from original searchstring from 'start' to 'end'
    subStringSearch = (char *)malloc(end - start);
    subReversed = (char *)malloc(end - start + 1);
    subFlipped = (char *)malloc(end - start + 1);
    subFlippedReversed = (char *)malloc(end - start + 1);
    
    subStringSearch = subString(searchstring,start,end);
    partialMatchSize = end - start;

    // Tree efficiency instrumentation
    reused_nodes = (unsigned int*) malloc(partialMatchSize*sizeof(int));

    
    /* 
       To support finding spots in file where partial search strings are found
       1.) Invade and destroy the original tree and rebuild it with new match_size
       2.) rebuild the tree for depth = start - end and use it for the partial search
    */
    
    initNode(head);
    
    if (buildTree(partialMatchSize,uniquenodes,reused_nodes,head,inname,verbose) != 0 ){
      
      //tree was not built correctly...
      return INVALID;
    }
      
    cout << "\nSearching for " << partialMatchSize << " characters (characters " << start << " to " << end-1 << ") from the Orig. String of " << searchstring << "\n";
    
    retval=MakeStringPermutations(subStringSearch,subReversed,subFlipped,subFlippedReversed);

    if (retval==INVALID) {
      return retval;
    }

    cout << "\n\nSearching for substring: " << subStringSearch << "\n";
    level=0;
    partial_searchTree(head, level, subStringSearch,start,end, partialMatchSize);
    
    cout << "\n\nSearching for subReversed string: " << subReversed << "\n";
    level=0;
    partial_searchTree(head, level, subReversed,start,end, partialMatchSize);
    
    cout << "\n\nSearching for subFlipped string: " << subFlipped << "\n";
    level=0;
    partial_searchTree(head, level, subFlipped,start,end, partialMatchSize);
    
    cout << "\n\nSearching for subFlippedReversed string: " << subFlippedReversed << "\n";
    level=0;
    partial_searchTree(head, level, subFlippedReversed,start,end,partialMatchSize);
    printf("\n");
    
    //Reset the start and end index values
    start = end = -1;
    
    //end of search for n character.
  } else {
    cout << "\nPartial match search skipped due to parameter errors.";
  }
  
  cout << "\n-------------------";
  free(subStringSearch);
  free(subReversed);
  free(subFlipped);
  free(subFlippedReversed);
  return 0;
}

// A wrapper for the parallel search code. This is the highest level function which takes a searchstring and calls helper functions to do parallel searches on it.
int parallelSearch(char *searchstring, struct node*head)
{
  pthread_t *threads;
  struct node_t **p;
  int n=0;
  int i=0;
  int MATCH_SIZE=0;
  int retval=0;
  int span=0;

  char *reversed;
  char *flipped;
  char *flippedreversed;

  unsigned long long end=0;

  struct matchList_str* prev=NULL;

  if (searchstring==NULL) {
    return INVALID;
  }

  MATCH_SIZE=strlen(searchstring);

  reversed = (char *) malloc(MATCH_SIZE+1);
  flipped = (char*) malloc(MATCH_SIZE+1);
  flippedreversed = (char*) malloc(MATCH_SIZE+1);

  retval=MakeStringPermutations(searchstring,reversed,flipped,flippedreversed );                                                                           
  
  if (retval==INVALID) {
    return retval;
  }

  cout << "\nPARALLEL SEARCH with " << NUM_THREADS << " threads.";

  threads = (pthread_t *) malloc( 4 * sizeof(pthread_t));
  p=(struct node_t**) malloc(sizeof(struct node_t*)* NUM_THREADS);
  
  while(n < NUM_THREADS){
    p[n]=(struct node_t*) malloc(sizeof(struct node_t));
    p[n]->id = n;
    p[n]->noproc = n+1;
    p[n]->head = head;
    p[n]->found=INVALID;
    p[n]->matchPtr=NULL;
    p[n]->i=0;

    switch (n) {
    case 0:
      p[n]->k=searchstring; // change this to be unique for each thread id
      break;
    case 1:
      p[n]->k=reversed;
      break;
    case 2:
      p[n]->k=flipped;
      break;
    case 3:
      p[n]->k=flippedreversed;
      break;
    default:
      cout << "\nInvalid value of n in parallel search.";
      break;
    }

    pthread_create(&threads[n], NULL, master, (void *)p[n]);
    n++;
  }

  // Wait for threads to complete
  for (i=0;i<n;i++) {
    pthread_join(threads[i], NULL);
  }

  end=getticks();
 
  // Report findings
  for (i=0; i < n; i++) {
    prev=NULL;
    if (p[i]->matchPtr !=NULL) {

      cout << "\nThread #" << i << " found a match for : " << p[i]->k << " at "; // << p[i]->found << " for " << p[i]->k;

      while (p[i]->matchPtr !=NULL) {

	cout << p[i]->matchPtr->matchposition << "\t";

	if (prev !=NULL) {
	  span = (p[i]->matchPtr->matchposition - prev->matchposition);

	  cout << " (Span:" << span << ") ";

	}

	prev=p[i]->matchPtr;
	//cout << "\nPrev: " << prev->matchposition << "\n";
	p[i]->matchPtr=p[i]->matchPtr->next;


      }
   } else {

      cout << "\nThread #" << i << " didn't find a match for " << p[i]->k;

    }
  }
  

  cout << "\nLeaving parallel search.";
  cout << "\n-------------------";

  free(p);
  free(threads);
  free(reversed);
  free(flipped);
  free(flippedreversed);

  return 0;
}

// This function constructs the tree containing the genome
int buildTree(int max_size, unsigned int &uniquenodes, unsigned int *reused_nodes, struct node *head, char *inname, unsigned int verbose)
{
  int i=0;
  int spot=0;
  int bytes=0;
  int totalbytes=0;
  struct node *addnode=NULL;
  unsigned int added=0;
  unsigned int previous_added=0;
  unsigned long long ignored=0;

  FILE *infile=0;

  cout << "\nmax_size: " << max_size;
  char *inputstring =   (char*)malloc(max_size+1);
  char *subStringText = (char*)malloc(max_size -1); // fixme: revisit this

  memset(inputstring, 0,  (max_size+1));
  memset(subStringText, 0,(max_size - 1)); // fixme: revisit this 

  if (inputstring==NULL || subStringText==NULL) {
    cout << "\nGot null string in buildTree.";
    return INVALID;
  }

  // Open the input file
  if (!(infile=fopen(inname, "r"))) {
    cout << "\nUnable to open file for reading.";
    return INVALID;
  }
  
  if (max_size < 3) {
    cout << "\nInvalid tree depth in buildTree: " << max_size << ". Need a size greater than 3.";
    return INVALID;
  }
  
  // Read in max_size, insert max_size chunk into tree, move file pointer ahead _one_ (not max_size) and repeat
  do {
    bytes=fread(inputstring, 1,max_size,infile);
  
    // Check for newline character in input text file
    for (i=0; i < max_size; i++) {
	
      if (inputstring[i]=='\n') {
	//cout << "\nFound a newline character in inputstring.";
	bytes--;
	inputstring[i]='\0';
      }
    }

    /*
    // If we've read less than max_size we need to handle those seperately
    if (bytes < max_size) {
      
      for (i=0; i < (max_size-1); i++) {                                   
	subStringText=subString(inputstring, i, (max_size -1));                          
	spot++;                                                             
	insertTree(subStringText, head, spot, uniquenodes, reused_nodes,verbose,added);       
      }                

      break;
    }
    */

    if (bytes < max_size) {
      break;
    }

    // Update total # of bytes read in
    
    totalbytes=totalbytes + (unsigned long long)bytes;
    
    //cout << "\ntotalbytes now: " << totalbytes << " for " << inputstring;
    
    // Add the string to the tree
    previous_added = added;
    addnode=insertTree(inputstring, head,spot,uniquenodes, reused_nodes, verbose, added);

    //cout << "\nAdded total: " << added << ". This time: " << (added - previous_added) << "."; 
    // If there was an error adding to the tree, error out
    if (addnode==NULL) {
      ignored++;
    }

    // Increment the location we read from in the file by 1 (not max_size)
    spot++;

    // Backtrack to the 'spot'
    fseek(infile, spot, SEEK_SET);

  } while (bytes == max_size);

  if (verbose==ENABLED) {
    cout << "\nComplete sub-strings in input file: " << spot << ". (Excludes sub-strings of size less than the match size.)";
    cout << "\nUnique sub-strings: " << uniquenodes;
    cout << "\nTotal bytes: " << totalbytes;
    cout << "\nTotal characters in the tree: " << added;
  }
  cout << "\n\n";

  cout << "\nIgnored: " << ignored;
  //  free(inputstring);
  free(subStringText);

  return 0;
}

// This function derives the other three permutations of the original search string (e.g. reversed, flipped (A<->T, C<->G), and flipped + reversed
int MakeStringPermutations(char *origString, char *reversed, char *flipped, char *flippedreversed)
{
  unsigned int i=0;
  int j=0;
  unsigned int len=0;
  
  if (origString==NULL) {
    return INVALID;
  }
  
  len=strlen(origString);

  // Generate reversed string (e.g. AAACCC --> CCCAAA)
  //  j=len -1;

  for (i=0, j=len-1; i < len; i++) {
    reversed[i]=origString[j];
    j--;
  }

  reversed[len]='\0';

  // Generate flipped string (e.g. ACTG --> TGAC) 
  // The rule is (A<-->T) and (C<-->G)
  for (i=0; i < len; i++) {
    switch (origString[i]) {
    case 'A':
      flipped[i]='T';
      break;
    case 'C':
      flipped[i]='G';
      break;
    case 'G':
      flipped[i]='C';
      break;
    case 'T':
      flipped[i]='A';
      break;
    default:
      cout << "\nInvalid character in MakeStringPermutations: " << origString[i];
      return INVALID;
    }
  }

  flipped[len]='\0';

  // Generate flipped reverse string (e.g. TGAC --> CAGT)
  for (i=0, j=len -1; i < len; i++) {
    flippedreversed[i]=flipped[j];
    j--;
  }

  flippedreversed[len]='\0';

  return 0;

}

char *subString(char *aString,int start,int end)
{
  char *subStringSearch = (char *)malloc(end-start); // fixme: does this get freed somewhere?

  int i;
  for(i = 0 ;i< (end-start);i++)
    {
      subStringSearch[i] = aString[start+i] ;
    }
  subStringSearch[i]='\0';
  return subStringSearch;
    
}

// Parallel search for a given string in the tree
int par_searchTree(struct node*&head, int level, char *searchstring, unsigned int MATCH_SIZE, struct matchList_str *&RetMatchPtr)
{
 
  struct matchList_str *matchPtr=NULL;
  node *cur=head;

  // No match found
  if (head==NULL) { 
    //cout << "\nUnable to find " << searchstring << ".";
    RetMatchPtr=NULL;
    return INVALID;
  }

  // Found a match
  if (level==(int)MATCH_SIZE ){ 
    //cout << "\n\t-->Found: " << searchstring << ".";
    matchPtr=cur->matchList;
    RetMatchPtr=matchPtr;
   return 0;  //parameter passing for thread function 
  }
 
  // Keep searching
  switch (searchstring[level]) {
  case 'A':
    level++;

    par_searchTree(cur->anext,level, searchstring,MATCH_SIZE, RetMatchPtr);
    break;
  case 'C':

    level++;

    par_searchTree(cur->cnext,level, searchstring,MATCH_SIZE, RetMatchPtr);
    break;
  case 'G':

    level++;

    par_searchTree(cur->gnext,level, searchstring,MATCH_SIZE, RetMatchPtr);
    break;
  case 'T':
    
    level++;
    
    par_searchTree(cur->tnext,level, searchstring,MATCH_SIZE, RetMatchPtr);
    break;
  default:
    cout << "\nUnexpected character found in search criteria: " << searchstring[level];
    break;
  }
  return 0; 
}
 
// Search for an exact match of a string in the tree (sequentially, not parallel)
int seq_searchTree(struct node*&head, int level, char *searchstring, unsigned int matchLength){
  struct matchList_str *matchPtr=NULL;
  node *cur=head;
  unsigned int prevmatch=0;
  int span=0;
 
  if (head==NULL) { // No match

    cout << "\t--> Unable to find " << searchstring << ".";

    return INVALID;
  }
 
  if (level==(int)matchLength ) {

    cout << "\t--> Found: " << searchstring << ".";

    /*
    // Currently we don't support finding the location of a match which isn't MATCH_SIZE so this output is disabled
    if (matchLength==MATCH_SIZE) {
      cout << "\n\t--> Positions in file: ";
    }
    */
    matchPtr=cur->matchList;
   
    while (matchPtr !=NULL) {

      cout << "\t" << matchPtr->matchposition;

      span = matchPtr->matchposition - prevmatch;
      if (span != matchPtr->matchposition) {

	cout << "\t(Span:" << span << ")";

      }
      prevmatch=matchPtr->matchposition;
      matchPtr=matchPtr->next;
    }
    return 0; // found what we were looking for and so we can exit
  }
 
  switch (searchstring[level]) {
  case 'A':

    level++;
    seq_searchTree(cur->anext,level, searchstring, matchLength);
    break;
  case 'C':

    level++;
    seq_searchTree(cur->cnext,level, searchstring, matchLength);
    break;
  case 'G':

    level++;
    seq_searchTree(cur->gnext,level, searchstring, matchLength);
    break;
  case 'T':
   
    level++;
    seq_searchTree(cur->tnext,level, searchstring, matchLength);
    break;
  default:
    cout << "\nUnexpected character found in search criteria: " << searchstring[level];
    break;
  }

  return 0;
}

// Search for a partial match of a string in the tree
int partial_searchTree(struct node*&head, int level, char *searchstring, int start, int end, unsigned int MATCH_SIZE)
{
  struct matchList_str *matchPtr=NULL;
  node *cur=head;
  unsigned int prevmatch=0;
  int span=0;
 
  if (head==NULL) { // No match
    cout << "\nUnable to find " << searchstring << " in the tree.";
    return INVALID;
  }
 
  if (level==(int)MATCH_SIZE || level == (end - start - 1)) { // Found a match
    cout << "Found: " << searchstring << " in the tree at level " << level;
    matchPtr=cur->matchList;
    
    while (matchPtr !=NULL) {
      cout << "\t" << matchPtr->matchposition;
      span = matchPtr->matchposition - prevmatch;
      if (span != matchPtr->matchposition) {
	cout << "\t(Span:" << span << ")";
      }
      prevmatch=matchPtr->matchposition;
      matchPtr=matchPtr->next;
    }
    return 0; // found what we were looking for and so we can exit
  }
 
  switch (searchstring[level]) {
  case 'A':
    level++;
    partial_searchTree(cur->anext,level, searchstring, start,end,MATCH_SIZE);
    break;
  case 'C':
    level++;
    partial_searchTree(cur->cnext,level, searchstring,start,end,MATCH_SIZE);
    break;
  case 'G':
    level++;
    partial_searchTree(cur->gnext,level, searchstring,start,end,MATCH_SIZE);
    break;
  case 'T':
    level++;
    partial_searchTree(cur->tnext,level, searchstring,start,end,MATCH_SIZE);
    break;
  default:
    cout << "\nUnexpected character found in search criteria: " << searchstring[level];
    break;
  }

  return 0;
}


// Print out the binary tree
int printTree(struct node*&head, char ch, int level, char *printout, unsigned int MATCH_SIZE, ofstream &ofs, int file_io)
{
  
  node *cur=head;
  struct matchList_str *matchPtr=NULL;
  unsigned int prevspot=0;
  int span=0;
  int match_count=0;

  if (head==NULL) {
    return INVALID;
  }

  if (level >=0) {
    printout[level]=ch;
  }
  
  if (level==(int)MATCH_SIZE-1) {

    printout[MATCH_SIZE]='\0';
    if (file_io==ENABLED) {
      ofs << "\n" << printout << "\t";
    } else {
      cout << "\n" << printout; //testing
    }

    matchPtr=cur->matchList;

    while (matchPtr !=NULL) {
      match_count++;
      /*
	if (file_io==ENABLED) {
	ofs << "\t" << matchPtr->matchposition;
	} else {
	cout << "\t" << matchPtr->matchposition;
	}
      */
      span = matchPtr->matchposition - prevspot; // calculate span
      /*
	if (span != matchPtr->matchposition) {
	if (file_io==ENABLED) {
	ofs << "\t( Span:" << span << ")";
	} else {
	cout << "\t( Span:" << span << ")";
	}
	}
      */
      prevspot=matchPtr->matchposition;
      matchPtr=matchPtr->next;
    }
    
    if (file_io==ENABLED) {
      //ofs <<  " Matches: " << match_count;
    } else {
      cout << " Matches: " << match_count;
    }
        
    level--;
    return INVALID;
  }

  level++;

  printTree(cur->anext,'A',level,printout,MATCH_SIZE, ofs, file_io);
  printTree(cur->cnext,'C',level,printout,MATCH_SIZE, ofs, file_io);
  printTree(cur->gnext,'G',level,printout,MATCH_SIZE, ofs, file_io);
  printTree(cur->tnext,'T',level,printout,MATCH_SIZE, ofs, file_io);

  if (level==(int)MATCH_SIZE-1) {
    level--;
  }
  return 0;
}


// Initialize a node with default values
int initNode(struct node *&thisnode)
{
  thisnode->anext=NULL;
  thisnode->cnext=NULL;
  thisnode->gnext=NULL;
  thisnode->tnext=NULL;
  
  thisnode->matchList=NULL;
  
  return 0;
}

// Place a chunk in the tree, record the starting location. 
struct node *insertTree(char *insertString, struct node *&head, int location, unsigned int &uniquenodes, unsigned int *reused_nodes, unsigned int verbose, unsigned int &added)
{
  int i;
  int stringlen=0;
  int add_count=added;
  struct node *cur=head;
  struct node *newnode=NULL;
  struct matchList_str *matchPtr=NULL;
  struct matchList_str *matchPtr_prev=NULL;


  if (insertString==NULL) {
    cout << "\nReceived null insertString in insertTree.";
    return NULL;
  }

  stringlen=strlen(insertString);

  for (i=0; i < stringlen; i++) {
    switch (insertString[i]) {
    case 'A':
    case 'a':
      if (cur->anext==NULL) {
	newnode = new node;
	if (newnode==NULL) {
	  cout << "\nError allocating memory. Location: " << location;
	  return NULL;
	}

	added++;
	initNode(newnode);
	cur->anext=newnode;
	cur=cur->anext;
      } else {
	cur=cur->anext;
	reused_nodes[i]++;
	//cout << "\n\tReused nodes on A now: " << reused_nodes[i] << ". i=" << i;
      }
      break;
    case 'C':
    case 'c':
      if (cur->cnext==NULL) {
	newnode = new node;
	
	if (newnode==NULL) {
	  cout << "\nError allocating memory. Location: " << location;
	  return NULL;
	}

	added++;
	initNode(newnode);
	cur->cnext=newnode;
	cur=cur->cnext;
      } else {
	cur=cur->cnext;
        reused_nodes[i]++;
	//cout << "\n\tReused nodes on C now: " << reused_nodes[i] << ". i=" << i;
      }
      break;
    case 'G':
    case 'g':
      if (cur->gnext==NULL) {
	newnode = new node;
	if (newnode==NULL) {
	  cout << "\nError allocating memory. Location: " << location;
	  return NULL;	}

	added++;
	initNode(newnode);
	cur->gnext=newnode;
	cur=cur->gnext;
      } else {
	cur=cur->gnext;
	reused_nodes[i]++;
	//cout << "\n\tReused nodes on G now: " << reused_nodes[i] << ". i=" << i;
      }
      
      break;
    case 'T':
    case 't':
      if (cur->tnext==NULL) {
	newnode = new node;
	if (newnode==NULL) {
		cout << "\nError allocating memory. Location: " << location;
		return NULL;
	}

	added++;
	initNode(newnode);
	cur->tnext=newnode;
	cur=cur->tnext;
      } else {
	cur=cur->tnext;
        reused_nodes[i]++;
	//cout << "\n\tReused nodes on T now: " << reused_nodes[i] << ". i=" << i;
      }
      break;
    case '\n':
    case ' ':
      // ignoring newline character
      return NULL;
      break;
    default:
      cout << "\nReceived unexpected character in insertTree: " << insertString[i];
      return NULL;
      break;
    }
    
    
  }

  // Determine if any new substrings were added to the tree
  if ( (added-add_count) ==0) { // Found a complete match of a sub-string of length MATCH_SIZE
    
    // Update location

    matchPtr=cur->matchList;
    while (matchPtr !=NULL) {
      matchPtr_prev=matchPtr;
      matchPtr=matchPtr->next;
    }

    matchPtr = new matchList_str;
    matchPtr->matchposition=location;
    if (matchPtr_prev !=NULL) {
      matchPtr_prev->next=matchPtr;
    }
    matchPtr->next=NULL;

#ifdef DEBUG
    cout << "\nFound match\t";
    
    // Print string
    for (i=0; i < (int)strlen(insertString); i++) {
      cout << insertString[i];
    }
    
    //Print previous matches
    cout << "\t";
    matchPtr = cur->matchList;

    while (matchPtr !=NULL) {
      cout << "\t" << matchPtr->matchposition;
      matchPtr=matchPtr->next;
    }

#endif     
    
  } else { // Added a substring for the first time (It's unique)
    uniquenodes++;

    matchPtr = cur->matchList;
    matchPtr = new matchList_str;
    cur->matchList = matchPtr;
    matchPtr->matchposition=location;
    matchPtr->next=NULL;
  
  }
  
  return cur;
}

void *master (void *arg)
{ 
  int result=0;
  struct node_t* p= (struct node_t*) arg;
  clocks[p->id]=getticks();
  result=par_searchTree(p->head, p->i, p->k,strlen(p->k), p->matchPtr);
  return 0;
}

int check_arg(int argnum, int num_args)
{
  if (argnum >= num_args) {
    return -1;
  }

  return 0;
}
